

use anyhow::Result;
use byteorder::{LittleEndian, ReadBytesExt, WriteBytesExt};
use std::io::Cursor;

// node format:
// | type | nkeys |  pointers  |   offsets  | key-values
// |  2B  |   2B  | nkeys * 8B | nkeys * 2B | ...

// key-value format:
// | klen | vlen | key | val |
// |  2B  |  2B  | ... | ... |

const HEADER: u32 = 4;

const BTREE_PAGE_SIZE: u32 = 4096;
const BTREE_MAX_KEY_SIZE: u32 = 1000;
const BTREE_MAX_VAL_SIZE: u32 = 3000;

struct BNode {
    data: Vec<u8>, // can be dumped to the disk
}

enum BNodeType {
    NODE = 1,
    LEAF = 2,
}
//let nodeType = BNodeType::LEAF;
//let number: u32 = color as u32;

struct BTree {
    // pointer (a nonzero page number)
    root: u64,
}

trait BTreeCallback {
    // callbacks for managing on-disk pages
    fn get(ptr: u64) -> BNode; // dereference a pointer
    fn new(node: BNode) -> u64; // allocate a new page
    fn del(ptr: u64) -> Result<()>; // deallocate a page
}

fn init() {
    //  HEADER=2 B type  + 2 B nkeys
    //  8     =pointers =nkeys * 8B=1*8
    //  2     =offsets  =nkeys * 2B=1*2
    //  4     =klen +vlen=2+2
    let node1max = HEADER + 8 + 2 + 4 + BTREE_MAX_KEY_SIZE + BTREE_MAX_VAL_SIZE;
    assert!(node1max <= BTREE_PAGE_SIZE);
}

#[allow(dead_code)]
impl BNode {
    /// 从pos 位置读取u16
    fn read_u16(&self, pos: u64) -> u16 {
        let mut reader = Cursor::new(&self.data);
        reader.set_position(pos);
        reader.read_u16::<LittleEndian>().unwrap()
    }

    /// 从pos 位置写入u16
    fn write_u16(&mut self, pos: u64, val: u16) {
        // 使用Cursor来模拟一个可写入的字节流
        let mut writer = Cursor::new(&mut self.data);
        writer.set_position(pos); // 设置写入的起始位置
        writer.write_u16::<LittleEndian>(val).unwrap();
    }

    /// 从pos 位置读取u64
    fn read_u64(&self, pos: u64) -> u64 {
        let mut reader = Cursor::new(&self.data);
        reader.set_position(pos);
        reader.read_u64::<LittleEndian>().unwrap()
    }

    /// 从pos 位置写入u64
    fn write_u64(&mut self, pos: u64, val: u64) {
        let mut writer = Cursor::new(&mut self.data);
        writer.set_position(pos);
        writer.write_u64::<LittleEndian>(val).unwrap();
    }

    // header
    /// 节点类型
    pub fn btype(&self) -> u16 {
        // [0,2) 为 type
        // return binary.LittleEndian.Uint16(self.data)
        self.read_u16(0)
    }
    /// 有多少个key
    pub fn nkeys(&self) -> u16 {
        // [2,4) 的 2字节 为 nkeys
        // return binary.LittleEndian.Uint16(node.data[2:4])
        self.read_u16(2)
    }
    /// 设置node 头部信息
    pub fn set_header(&mut self, btype: BNodeType, nkeys: u16) {
        // 把type 保存到 前[0,2)个字节
        // binary.LittleEndian.PutUint16(self.data[0:2], btype)
        // 把nkeys 保存到  [2,4) 字节
        // binary.LittleEndian.PutUint16(self.data[2:4], nkeys)

        self.write_u16(0, btype as u16);
        self.write_u16(2, nkeys);
    }

    // pointers
    /// 获取第idx个指针
    pub fn get_ptr(&self, idx: u16) -> u64 {
        // 索引必须小于 nkeys
        assert!(idx < self.nkeys());
        // 偏移位置=HEADER(2+2)+ idx *8B
        let pos = HEADER + 8 * idx as u32;
        // 从偏移位置读取 8B 返回 uint64
        // return binary.LittleEndian.Uint64(node.data[pos:])

        self.read_u64(pos as u64)
    }
    /// 把第idx指针设置为val
    pub fn set_ptr(&mut self, idx: u16, val: u64) {
        // 索引必须小于 nkeys
        assert!(idx < self.nkeys());
        // 偏移位置=HEADER(2+2)+ idx *8B
        let pos = HEADER + 8 * idx as u32;
        // 从偏移位置 设置数据
        // binary.LittleEndian.PutUint64(node.data[pos:], val)
        self.write_u64(pos as u64, val)
    }

    // offset list
    /// 获取第idx 个位置
    pub fn offset_pos(&self, idx: u16) -> u16 {
        // idx 必须>=1 且小于 nkeys
        assert!(1 <= idx && idx <= self.nkeys());
        // HEADER(4) +nkeys *8B +(idx-1)*2B,第一个KV对的偏移量不保存在列表中(idx-1)
        HEADER as u16 + 8 * self.nkeys() + 2 * (idx - 1)
    }
    /// 获取第idx个偏移
    pub fn get_offset(&self, idx: u16) -> u16 {
        if idx == 0 {
            return 0;
        }
        // 从 offsetPos 的开始读取2B
        // return binary.LittleEndian.Uint16(node.data[offsetPos(node, idx):])
        let pos = self.offset_pos(idx);
        self.read_u16(pos as u64)
    }
    /// 设置第idx 个偏移
    pub fn set_offset(&mut self, idx: u16, offset: u16) {
        // 把 offset  保存到 指定的idx 位置
        let pos = self.offset_pos(idx);
        // binary.LittleEndian.Putu16(node.data[offsetPos(node, idx):], offset)
        self.write_u16(pos as u64, offset);
    }

    // key-values
    pub fn kv_pos(&self, idx: u16) -> u16 {
        let nkeys = self.nkeys();
        // idx 必须小于 nkeys
        assert!(idx <= nkeys);
        // HEADER(4) +nkeys*8B+nkeys*2B+相对于数据开始的偏移
        HEADER as u16 + 8 * nkeys + 2 * nkeys + self.get_offset(idx)
    }
    /// 获取第idx 个key
    pub fn get_key(&self, idx: u16) -> &[u8] {
        // idx 必须小于 nkeys
        assert!(idx < self.nkeys());
        //找到 kv 的位置
        let pos = self.kv_pos(idx);
        //读取2B  klen
        let klen = self.read_u16(pos as u64); //binary.LittleEndian.u16(node.data[pos:])
                                              // 从 pos+  2B klen  +  2B vlen 开始 读取 klen 长度的数据 作为key
                                              // 从node.data 获取 pos+4 到末尾的数组,然后从这个数组获取 0到klen的数据
                                              // return node.data[pos+4:][:klen]
        let start = (pos + 4) as usize;
        let end = start + klen as usize;
        let data = &self.data[start..end];
        data
    }
    /// 获取第idx 个value
    pub fn get_val(&self, idx: u16) -> &[u8] {
        // idx 必须小于 nkeys
        assert!(idx < self.nkeys());
        //找到 kv 的位置
        let pos = self.kv_pos(idx);
        //读取2B  klen
        let klen = self.read_u16(pos as u64); // binary.LittleEndian.u16(node.data[pos+0:])
                                              //读取2B  vlen
        let vlen = self.read_u16((pos + 2) as u64); //binary.LittleEndian.Uint16(node.data[pos+2:])
                                                    // 读取value
                                                    //return node.data[pos+4+klen:][:vlen]
        let start = (pos + 4 + klen) as usize;
        let end = start + vlen as usize;
        let data = &self.data[start..end];
        data
    }

    /// node size in bytes
    pub fn nbytes(&self) -> u16 {
        return self.kv_pos(self.nkeys());
    }
}

/// returns the first kid node whose range intersects the key. (kid[i] <= key)
// TODO: bisect
fn node_lookup_le(node: BNode, key: &[u8]) -> u16 {
    // 获取key 的数量
    let nkeys = node.nkeys();
    // 返回索引位置
    let mut found = 0;
    // the first key is a copy from the parent node,
    // thus it's always less than or equal to the key.
    // key 0 被跳过 所以从key 1 开始
    // for i = 1; i < nkeys; i++ {
    //     cmp := bytes.Compare(node.getKey(i), key)
    //     if cmp <= 0 {
    //         found = i
    //     }
    //     if cmp >= 0 {
    //         break
    //     }
    // }
    // return found

    for i in 1..nkeys {
        let cmp = node.get_key(i) <= key;
        if cmp {
            //如果获取的值 <=key 则重置found,否则终止查找
            found = i
        }
        if !cmp {// 当前值>key ，终止查询
            break;
        }
    }
    found
}

/// copy multiple KVs into the position
fn node_append_range(new: &mut BNode, old: &BNode, dst_new: u16, src_old: u16, n: u16) {
    assert!(src_old + n <= old.nkeys());
    assert!(dst_new + n <= new.nkeys());
    if n == 0 {
        return;
    }
    // copy pointers  复制 key指向 子节点的指针
    for i in 0..n {
        new.set_ptr(dst_new + i, old.get_ptr(src_old + i))
    }
    // copy offsets   kv 对的偏移
    let dst_begin = new.get_offset(dst_new);
    let src_begin = old.get_offset(src_old);
    // NOTE: the range is [1, n]，不是从0 开始
    let mut offset = 0;
    for i in 1..n {
        offset = dst_begin + old.get_offset(src_old + i) - src_begin;
        new.set_offset(dst_new + i, offset);
    }
    // copy KVs      实际key和value
    let begin = old.kv_pos(src_old) as usize;
    let end = old.kv_pos(src_old + n) as usize;
    // func copy(dst, src []T) int
    // copy(new.data[new.kvPos(dstNew):], old.data[begin:end])
    // rust 这样实现行吗
    let new_begin = new.kv_pos(dst_new) as usize;
    //unsafe {
    //    std::ptr::copy(&old.data[begin..end].as_ptr(), & new.data[new_begin..].as_mut_ptr(), end -begin);
    //}
    // use bytes::{BytesMut, BufMut};
    // 参考文档 https://docs.rs/bytes/latest/bytes/struct.BytesMut.html#method.copy_from_slice
    let _ = &new.data[new_begin..].copy_from_slice(&old.data[begin..end]);
}

/// copy a KV into the position
fn node_append_kv(new: &mut BNode, idx: u16, ptr: u64, key: &[u8], val: &[u8]) {
    // ptrs    设置这个key 对应的指针
    new.set_ptr(idx, ptr);
    // KVs     写入kv 值
    let pos = new.kv_pos(idx);
    // binary.LittleEndian.PutUint16(new.data[pos+0:], uint16(len(key)))
    // binary.LittleEndian.PutUint16(new.data[pos+2:], uint16(len(val)))
    new.write_u16((pos + 0) as u64, key.len() as u16);
    new.write_u16((pos + 2) as u64, val.len() as u16);
    // copy(new.data[pos+4:], key)
    // copy(new.data[pos+4+uint16(len(key)):], val)
    let _ = &new.data[(pos as usize + 4)..].copy_from_slice(key);
    let _ = &new.data[(pos as usize + 4 + key.len())..].copy_from_slice(val);
    // 计算偏移
    // the offset of the next key
    //new.setOffset(idx+1, new.getOffset(idx)+4+uint16((len(key)+len(val))))
    new.set_offset(
        idx + 1,
        new.get_offset(idx) + 4 + (key.len() as u16 + val.len() as u16),
    )
}

/// add a new key to a leaf node
fn leaf_insert(new: &mut BNode, old: &BNode, idx: u16, key: &[u8], val: &[u8]) {
    new.set_header(BNodeType::LEAF, old.nkeys() + 1);
    // 把前 idx 复制过来
    node_append_range(new, old, 0, 0, idx);
    // 在 idx 插入新节点
    node_append_kv(new, idx, 0, key, val);
    // 把old idx后边的数据 拷贝到 new 的idx+1 位置
    node_append_range(new, old, idx + 1, idx, old.nkeys() - idx)
}

/// update an existing key from a leaf node
fn leaf_update(new: &mut BNode, old: &BNode, idx: u16, key: &[u8], val: &[u8]) {
    new.set_header(BNodeType::LEAF, old.nkeys());
    node_append_range(new, old, 0, 0, idx);
    node_append_kv(new, idx, 0, key, val);
    node_append_range(new, old, idx + 1, idx + 1, old.nkeys() - (idx + 1));
}
